//最少硬币找零问题
function minCoinChange(coins, amount) {
    let dp = new Array(amount + 1).fill(Infinity);//Infinity表示正无穷大，这个数组 dp 用来存储每个金额对应的最小硬币数
    dp[0] = 0;
    for (let i = 1; i <= amount; i++) {
        for (let j = 0; j < coins.length; j++) {
            if (coins[j] <= i) {
                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);//dp[1]=1,dp[2]=dp[1]+1=2,dp[2]=1
            }
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
}

// 例子
let coins = [1, 2, 5];
let amount = 7;
let result = minCoinChange(coins, amount);
console.log("最少需要的硬币数量是：" + result);
//背包问题
function knapsack(weights, values, capacity) {
    const n = weights.length;
    const dp = new Array(n + 1).fill(0).map(() => new Array(capacity + 1).fill(0));

    for (let i = 1; i <= n; i++) {
        for (let w = 1; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(
                     values[i - 1] + dp[i - 1][w - weights[i - 1]],
                    dp[i - 1][w]
                );
            } else {
                dp[i][w] = dp[i - 1][w]; 
                 
            }
        }
    }

    return dp[n][capacity];
}

const weights = [1, 3, 4, 5];
const values = [1, 4, 5, 7];
const capacity = 7;

console.log(knapsack(weights, values, capacity)); // 输出最大价值
//最长公共子序列
function longestCommonSubsequence(text1, text2) {
    const m = text1.length;
    const n = text2.length;
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[m][n];
}
const text1 = "abcde";
const text2 = "ace";
console.log(longestCommonSubsequence(text1, text2)); // 输出最长公共子序列的长度
//贪心算法（最小硬币找零问题）
function makeChange(coins, amount) {
    coins.sort((a, b) => b - a); // 将硬币按面额从大到小排序
    let coinCount = 0;

    for (let i = 0; i < coins.length; i++) {
        while (amount >= coins[i]) {
            amount -= coins[i];
            coinCount++;
        }
    }

    if (amount !== 0) {
        return -1; // 无法凑出指定金额
    }

    return coinCount;
}

const coins1 = [1, 2, 5];
const amount1 = 11;
console.log(makeChange(coins1, amount1)); // 输出所需的最少硬币数量
//分数背包问题
function fractionalKnapsack(weights, values, capacity) {
    const n = weights.length;
    const density = new Array(n);
    for (let i = 0; i < n; i++) {
        density[i] = { index: i, value: values[i] / weights[i] };
    }
    density.sort((a, b) => b.value - a.value);

    let maxTotalValue = 0;
    for (let i = 0; i < n; i++) {
        if (weights[density[i].index] <= capacity) {
            maxTotalValue += values[density[i].index];
            capacity -= weights[density[i].index];
        } else {
            maxTotalValue += density[i].value * capacity;
            break;
        }
    }
    return maxTotalValue;
}

const weights2 = [10, 20, 30];
const values2 = [60, 100, 120];
const capacity2 = 50;
console.log(fractionalKnapsack(weights2, values2, capacity2)); // 输出最大总价值